package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-05 11:02
 **/
public class LeetCode5944 {

    //最近公共祖先节点
    TreeNode ancestor;

    public String getDirections(TreeNode root, int startValue, int destValue) {
        dfs(root, startValue, destValue);
        List<String> list = new ArrayList<>();
        findNode(ancestor, startValue, list);
        List<String> list2 = new ArrayList<>();
        findNode(ancestor, destValue, list2);
        StringBuilder builder = new StringBuilder();
        //找startValue节点的路径只要知道节点个数即可，全部加"U"即可
        int size = list.size();
        for (int i = 0; i < size; i++) {
            builder.append("U");
        }

        //append寻找destValue的路径
        for (String s : list2) {
            builder.append(s);
        }

        return builder.toString();
    }

    //寻找最近公共父节点
    boolean dfs(TreeNode root, int startValue, int destValue) {
        if (root == null) {
            return false;
        }

        boolean lson = dfs(root.left, startValue, destValue);
        boolean rson = dfs(root.right, startValue, destValue);

        if (lson && rson || ((root.val == startValue || root.val == destValue) && (lson || rson))) {
            ancestor = root;
        }
        return lson || rson || root.val == startValue || root.val == destValue;
    }

    //添加路径
    boolean findNode(TreeNode root, int val, List<String> list) {
        if (root == null) {
            return false;
        }
        if (val == root.val) {
            return true;
        }
        list.add("L");
        boolean flag1 = findNode(root.left, val, list);
        if (flag1) {
            return true;
        }
        list.remove(list.size() - 1);
        list.add("R");
        boolean flag2 = findNode(root.right, val, list);
        if (flag2) {
            return true;
        }
        list.remove(list.size() - 1);
        return false;
    }

}
